#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int data;
  struct node* left;
  struct node* right;
} Node;

typedef struct
{
  Node* root;
} Tree;

// 前序遍历
void preorder(Node* node)
{
  if (node != NULL)
  {
    // 出口
    printf("%d\n", node->data);
    // 递归关系
    preorder(node->left);
    preorder(node->right);
  }
}

// 中序遍历
void inorder(Node* node)
{
  if (node != NULL)
  {
    // 递归关系
    inorder(node->left);
    // 出口
    printf("%d\n", node->data);
    // 递归关系
    inorder(node->right);
  }
}

// 后序遍历
void postorder(Node* node)
{
  if (node != NULL)
  {
    postorder(node->left);
    postorder(node->right);
    printf("%d\n", node->data);
  }
}

void insert(Tree* tree, int value)
{
  // value打包成一个节点
  Node* node = malloc(sizeof(Node));
  node->data = value;
  node->left = NULL;
  node->right = NULL;

  // 若这个BST没有根，直接把value放在根节点
  if (tree->root == NULL)
  {
    tree->root = node;
  }
  // 左右子树看下合适的位置
  else
  {
    // temp就是当前我的value需要跟哪个节点作比较
    Node* temp = tree->root;
    while (temp != NULL)  // 当temp不为空，不断作比较
    {
      // 没有重复数字的前提
      if (value < temp->data)
      {
        // 当左边的节点为空时直接插入
        if (temp->left == NULL)
        {
          temp->left = node;
          // 插入之后直接return不用再看
          return;
        }
        else  // 如果不为空的话要让temp跑到左分支继续探测
        {
          temp = temp->left;
        }
      }
      else  // 插入到右边的情况
      {
        // 同理右边，若为空
        if (temp->right == NULL)
        {
          temp->right = node;
          return;
        }
        else
        {
          // 继续向右边探测
          temp = temp->right;
        }
      }
    }
  }
}

// 树的高度
// 递推关系：减而治之
// 树的高度=max(左子树的高度+1，右子树的高度+1)

int get_height(Node* node)
{
  if (node == NULL)
  {
    return 0;
  }
  else
  {
    // return max(get_height(node->left) + 1, get_height(node->right) + 1);
    int left_h = get_height(node->left);
    int right_h = get_height(node->right);
    int max = left_h;
    if (right_h > max)
    {
      max = right_h;
    }
    return max + 1;
  }
}

// 求任何一棵树的最大值
// 递归关系：最大值=amx(本节点,左子数最大值，右子树最大值）
int get_maximum(Node* node)
{
  if (node == NULL)
  {
    return -1;
  }
  else
  {
    int m1 = get_maximum(node->left);
    int m2 = get_maximum(node->right);
    int m3 = node->data;
    int max = m1;
    if (m2 > max)
    {
      max = m2;
    }
    if (m3 > max)
    {
      max = m3;
    }
    return max;
  }
}

int main()
{
  int arr[7] = {6, 3, 8, 2, 5, 1, 7};
  Tree tree;
  tree.root = NULL;
  int i;
  for (size_t i = 0; i < 7; i++)
  {
    insert(&tree, arr[i]);
  }

  // preorder(tree.root);
  // inorder(tree.root);
  // int height = get_height(tree.root);
  // printf("h=%d\n", height);
  int max = get_maximum(tree.root);
  printf("m=%d\n", max);
}
